/*
 * @lc app=leetcode.cn id=797 lang=typescript
 *
 * [797] 所有可能的路径
 */

// @lc code=start
function allPathsSourceTarget(graph: number[][]): number[][] {
  const m = graph.length;
  // 已访问过的节点
  const visited = new Array(m).fill(0);
  const backtrack = (idx: number, path: number[] = []) => {
    visited[idx] = 1;
    path.push(idx);
    // 已经到达目标，更新答案，退出递归
    if (idx === m - 1) {
      ans.push([...path]);
      return;
    }
    // 遍历下一次选择
    for (const to of graph[idx]) {
      if (visited[to]) continue;
      backtrack(to, path);
      visited[to] = 0;
      path.pop();
    }
  };
  const ans: number[][] = [];
  backtrack(0);
  return ans;
}
// @lc code=end
